Loading AI tools
来自维基百科,自由的百科全书
可計算性理論裡,編號(英語:numbering、indexing等)是將一個集合的元素(如函數、有理數、圖、或形式語言的字串)編上自然數號碼。可計算性[1]以及相關的概念最先定義在自然數上,而利用編號,可將這些概念傳遞到上述的其他集合中作討論。
集合的一個編號是由到的,滿的偏函數[2]:477。編號在數字的取值(若有定義)一般以表示(而不是常見的函數表示)。
編號的例子有:
如果一個編號是全函數,則它是全的[3]:98。如果偏編號的定義域是遞歸可枚舉的話,則必存在等價的全編號,等價性的定義將在下節給出。
若集合可判定,則編號可判定。
如果當且僅當,則編號是單值的[3]:98;換言之,是一個單射函數。偏可計算函數構成的集合上的單值編號又稱費德伯格編號。
所有編號構成的集合上可以定義預序。令和是兩編號,則可歸約到,記為,當且僅當存在一元偏可計算函數,使得
若而且,則等價於,記為。[3]:100
如果被編號的對象足夠「可構」,人們常常會考慮能高效解碼的編號[2]:486。例如,若集合遞歸可枚舉,則編號是可計算的當且僅當滿足的二元組構成的集合遞歸可枚舉。類似地,偏函數的編號是可計算的當且僅當關係「」是偏遞歸的[2]:487。
若某集合上任意可計算編號都可歸約到特定編號,則稱該特定編號為主的。所有的遞歸可枚舉子集以及所有偏可計算函數都有主編號[2]:487。偏遞歸函數上的主編號又稱為可接受編號。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.